#include <bits/stdc++.h>

using namespace std;

class Solution {
private:
//    int calcXor(vector<int> &arr, int start, int end) {
//        int ret = arr[start];
//        for (int i = start + 1; i <= end; ++i)
//            ret ^= arr[i];
//        return ret;
//    }

    int bitCount[301][24] = {0};

public:
//    int countTriplets(vector<int> &arr) { //version 1:暴力
//        int counter = 0;
//        int len = arr.size();
//        for (int k = 1; k < len; ++k)
//            for (int j = 0; j <= k; ++j)
//                for (int i = 0; i < j; ++i) {
//                    int a = calcXor(arr, i, j - 1);
//                    int b = calcXor(arr, j, k);
//                    counter += a == b;
//                }
//        return counter;
//    }

//    int countTriplets(vector<int> &arr) { //version 2
//        int counter = 0;
//        int len = arr.size();
//        int tmp = arr[0];
//        for (int j = 0; j < 24; ++j) {
//            bitCount[1][j] = tmp & 1;
//            tmp >>= 1; //右移，取每一位
//        }
//        for (int i = 2; i <= len; ++i) {
//            tmp = arr[i - 1];
//            for (int j = 0; j < 24; ++j) {
//                bitCount[i][j] = bitCount[i - 1][j] + (tmp & 1); //前缀和，便于查询区间内有多少个1
//                tmp >>= 1; //右移，取每一位
//            }
//        }
//        for (int k = 2; k <= len; ++k) {
//            for (int j = 1; j <= k; ++j)
//                for (int i = 1; i < j; ++i) {
//                    int b = 0;
//                    for (b; b < 24; ++b) {
//                        int xor_1 = bitCount[j - 1][b] - bitCount[i - 1][b];
//                        int xor_2 = bitCount[k][b] - bitCount[j - 1][b];
//                        if (abs(xor_1 - xor_2) & 1) {
//                            break;
//                        }
//                    }
//                    if (b == 24) {
//                        ++counter;
//                    }
//                }
//        }
//        return counter;
//    }
    int countTriplets(vector<int> &arr) { //version 3
        int len = arr.size();
        int counter = 0;
        int *sum = new int[len + 1];
        sum[0] = 0;
        map<int, vector<int> *> hashTable;
        hashTable[0] = new vector<int>();
        hashTable[0]->push_back(0);
        for (int i = 1; i <= len; ++i) {
            int newSum = sum[i - 1] ^arr[i - 1];
            sum[i] = newSum;
            if (hashTable.find(newSum) == hashTable.end()) {
                hashTable[newSum] = new vector<int>();
            }
            vector<int> *thisVector = hashTable[newSum];
            for (auto it = thisVector->begin(); it != thisVector->end(); ++it) {
                counter += i - (*it) - 1;
            }
            thisVector->push_back(i);
        }
        return counter;
    }
};

int main() {
    vector<int> a = {2, 3, 1, 6, 7};
    Solution solution;
    cout << solution.countTriplets(a);
    return 0;
}
